#include "Format.h"

class QuickSort {
public:
    QuickSort();

    QuickSort(int *arr, int num) {
        QuickSort();
        this->sort(arr, 0, num - 1);
        Format::format(arr, num);
    }
    ~QuickSort();

private:
    int sort(int *arr, int low, int high);
};

QuickSort::QuickSort() {
}

QuickSort::~QuickSort() {
}

int QuickSort::sort(int *arr, int low, int high) {
    int compareCount = 0, moveCount = 0;
    moveCount += 2;
    if (low >= high) {
        return 0;
    }
    compareCount++;
    int first = low;
    int last = high;
    int key = arr[first]; /*���ֱ�ĵ�һ����¼��Ϊ�ڱ�*/
    moveCount += 3;
    while (first < last) {
        while (first < last && arr[last] >= key) {
            //�Ӻ��濪ʼ�������ڱ���Ĳ������ƶ�lastָ��
            last--;
            moveCount++;
            compareCount++;
        }
        compareCount++;
        arr[first] = arr[last]; /*���ȵ�һ��С���Ƶ��Ͷ�*/
        moveCount++;
        while (first < last && arr[first] <= key) {
            //�Ӻ��濪ʼ�������ڱ�С�Ĳ������ƶ�firstָ��
            first++;
            moveCount++;
            compareCount++;
        }
        compareCount++;
        arr[last] = arr[first];
        moveCount++;
        compareCount++;
        /*���ȵ�һ������Ƶ��߶�*/
    }
    compareCount++;
    arr[first] = key; /*�ڱ���䵽����λ��*/
    moveCount++;
    sort(arr, low, first - 1); //���ڱ�ǰ�沿�ֽ������
    sort(arr, first + 1, high); //���ڱ����沿�ֽ������

    arr[TestNumber] += moveCount;
    arr[TestNumber + 1] += compareCount;

    return 0;
}



